package 密码学实验;

import java.math.BigInteger;

public class BlumBlumShub {
    private BigInteger state;
    private final BigInteger n;

    // 使用两个大素数初始化
    public BlumBlumShub(BigInteger p, BigInteger q, long seed) {
        // n = p * q (p和q都是模4余3的素数)
        this.n = p.multiply(q);
        this.state = BigInteger.valueOf(seed).mod(n);
    }

    public int nextBit() {
        // X_{i+1} = X_i^2 mod n
        state = state.modPow(BigInteger.TWO, n);
        return state.testBit(0) ? 1 : 0; // 返回最低有效位
    }

    public int nextInt(int bits) {
        int value = 0;
        for (int i = 0; i < bits; i++) {
            value = (value << 1) | nextBit();
        }
        return value;
    }

    public static void main(String[] args) {
        // 使用模4余3的素数
        BigInteger p = new BigInteger("11");
        BigInteger q = new BigInteger("19");
        BlumBlumShub bbs = new BlumBlumShub(p, q, System.currentTimeMillis());

        System.out.println("生成10个随机整数:");
        for (int i = 0; i < 10; i++) {
            System.out.println(bbs.nextInt(16)); // 16位随机数
        }
    }
}